home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / general / procssng / ccs / ccs-11tl.lha / lbl / xview / hview / 24to8.c next >
Encoding:
C/C++ Source or Header  |  1992-07-14  |  31.0 KB  |  1,366 lines
  1. #include <stdio.h>
  2. #include <sys/types.h>
  3.  
  4. #include <X11/Xlib.h>
  5. #include <X11/Xutil.h>
  6.  
  7. #include <hipl_format.h>
  8.  
  9. byte      r[256], g[256], b[256];     
  10.  
  11. extern char     *myname;        /* program name for printf's */
  12.  
  13. /***************************************************************/
  14. /***************************************************************/
  15.  
  16. /*
  17.  * xv24to8.c  -  contains the 24-to-8-bit Conv24to8 procedure
  18.  *
  19.  * The Conv24to8 procedure takes a pointer to a 24-bit image (loaded
  20.  * previously).  The image will be a w * h * 3 byte array of
  21.  * bytes.  The image will be arranged with 3 bytes per pixel (in order
  22.  * R, G, and B), pixel 0 at the top left corner.  (As normal.)
  23.  * The procedure also takes a maximum number of colors to use (numcols)
  24.  *
  25.  * The Conv24to8 procedure will set up the following:  it will allocate and
  26.  * create 'pic', a pWIDE*pHIGH 8-bit picture.  it will set up pWIDE and pHIGH.
  27.  * it will load up the r[], g[], and b[] colormap arrays.  it will NOT
  28.  * calculate numcols, since the cmap sort procedure has to be called anyway
  29.  *
  30.  * Conv24to8 returns '0' if successful, '1' if it failed (presumably on a
  31.  * malloc())
  32.  *
  33.  * contains:
  34.  *   Cont24to8()
  35.  *   Init24to8()
  36.  */
  37.  
  38. #define    MAX_CMAP_SIZE    256
  39. #define    COLOR_DEPTH    8
  40. #define    MAX_COLOR    256
  41. #define    B_DEPTH        5    /* # bits/pixel to use */
  42. #define    B_LEN        (1<<B_DEPTH)
  43. #define    C_DEPTH        2
  44. #define    C_LEN        (1<<C_DEPTH)    /* # cells/color to use */
  45. #define RANGE(a,b,c) { if (a < b) a = b;  if (a > c) a = c; }
  46.  
  47. typedef struct colorbox {
  48.     struct colorbox *next, *prev;
  49.     int       rmin, rmax, gmin, gmax, bmin, bmax;
  50.     int       total;
  51. }         CBOX;
  52.  
  53. typedef struct {
  54.     int       num_ents;
  55.     int       entries[MAX_CMAP_SIZE][2];
  56. }         CCELL;
  57.  
  58. static byte *pic24, *pic;
  59. static int num_colors, WIDE, HIGH, pWIDE, pHIGH;
  60. static int histogram[B_LEN][B_LEN][B_LEN];
  61.  
  62. CBOX     *freeboxes, *usedboxes;
  63. CCELL   **ColorCells;
  64.  
  65. static void get_histogram();
  66. static CBOX *largest_box();
  67. static void splitbox();
  68. static void shrinkbox();
  69. static void assign_color();
  70. static CCELL *create_colorcell();
  71. static void map_colortable();
  72. static int quant_fsdither();
  73. static int Quick24to8();
  74. static int QuickCheck();
  75.  
  76. static int tbl1[512],        /* tables used in F-S Dithering */
  77.           tbl3[512],        /* contain i/16, 3i/16, 5i/16, 7i/16, */
  78.           tbl5[512],        /* (i=-256..255) respectively */
  79.           tbl7[512];
  80.  
  81. int       slow24 = 0;
  82.  
  83. /****************************/
  84. void
  85. Init24to8()
  86. /****************************/
  87. {
  88.     /* initialize Floyd-Steinberg division tables */
  89.     /* make sure rounding is done correctly for negative values! */
  90.  
  91.     int       i;
  92.  
  93.     for (i = -256; i < 0; i++) {
  94.     tbl1[i + 256] = -((8 - i) / 16);
  95.     tbl3[i + 256] = -((8 - 3 * i) / 16);
  96.     tbl5[i + 256] = -((8 - 5 * i) / 16);
  97.     tbl7[i + 256] = -((8 - 7 * i) / 16);
  98.     }
  99.  
  100.     for (i = 0; i < 256; i++) {
  101.     tbl1[i + 256] = (i + 8) / 16;
  102.     tbl3[i + 256] = (3 * i + 8) / 16;
  103.     tbl5[i + 256] = (5 * i + 8) / 16;
  104.     tbl7[i + 256] = (7 * i + 8) / 16;
  105.     }
  106. }
  107.  
  108.  
  109.  
  110. /****************************/
  111. int
  112. Conv24to8(p, op, w, h, nc, mono, rr, gg, bb)
  113. /****************************/
  114.     byte     *p, *op;
  115.     int       w, h, nc, mono;
  116.     byte     *rr, *gg, *bb;
  117. {
  118.     int       i, rval;
  119.     CBOX     *box_list, *ptr;
  120.  
  121.     /* copy arguments to local-global variables */
  122.     pic24 = p;
  123.     pWIDE = WIDE = w;
  124.     pHIGH = HIGH = h;
  125.     num_colors = nc;
  126.  
  127.  
  128.     /*
  129.      * allocate pic immediately, so that if we can't allocate it, we don't
  130.      * waste time running this algorithm
  131.      */
  132.  
  133.     pic = op;
  134.     if (pic == NULL) {
  135.     fprintf(stderr, "%s: Conv24to8() - failed to allocate 'pic'\n", myname);
  136.     return (0);
  137.     }
  138.     /*
  139.      * quick check:  if we're going to display a greyscale or 1-bit image,
  140.      * DON'T run this annoyingly time-consuming code.  Just convert the
  141.      * 24-bit color image to an 8-bit greyscale.  This takes virtually no
  142.      * time, by comparision, and it has the same effect.
  143.      */
  144.  
  145.     if (mono /* || nc==0 */ ) {
  146.     byte     *pp, *p24;
  147.  
  148.     for (i = 0; i < 256; i++)
  149.         r[i] = g[i] = b[i] = i;    /* greyscale colormap */
  150.     pp = pic;
  151.     p24 = pic24;
  152.     for (i = WIDE * HIGH; i > 0; i--, pp++, p24 += 3)
  153.         /* pp=.33R+.5G+.17B */
  154.         *pp = (p24[0] * 11 + p24[1] * 16 + p24[2] * 5) >> 5;
  155.  
  156.     get_global_cmap(rr, gg, bb);
  157.     return (num_colors);
  158.     }
  159.     if (QuickCheck(pic24, w, h, nc)) {
  160.     /* see if it's a <256 color RGB pic */
  161.     fprintf(stderr, "No color compression was necessary.\n");
  162.     get_global_cmap(rr, gg, bb);
  163.     return num_colors;
  164.     } else if (!slow24) {
  165.     fprintf(stderr, "Doing quick 24-bit to 8-bit conversion....\n");
  166.     rval = Quick24to8(pic24, w, h);
  167.     get_global_cmap(rr, gg, bb);
  168.     return (num_colors);
  169.     } else
  170.     fprintf(stderr, "Doing full 24-bit to 8-bit conversion.....\n");
  171.  
  172.     /**** STEP 1:  create empty boxes ****/
  173.  
  174.     usedboxes = NULL;
  175.     box_list = freeboxes = (CBOX *) malloc(num_colors * sizeof(CBOX));
  176.  
  177.     if (box_list == NULL) {
  178.     fprintf(stderr, "%s: Conv24to8() - failed to allocate 'freeboxes'\n", myname);
  179.     return (0);
  180.     }
  181.     for (i = 0; i < num_colors; i++) {
  182.     freeboxes[i].next = &freeboxes[i + 1];
  183.     freeboxes[i].prev = &freeboxes[i - 1];
  184.     }
  185.     freeboxes[0].prev = NULL;
  186.     freeboxes[num_colors - 1].next = NULL;
  187.  
  188.  
  189.     /**** STEP 2: get histogram, initialize first box ****/
  190.  
  191.     ptr = freeboxes;
  192.     freeboxes = ptr->next;
  193.     if (freeboxes)
  194.     freeboxes->prev = NULL;
  195.  
  196.     ptr->next = usedboxes;
  197.     usedboxes = ptr;
  198.     if (ptr->next)
  199.     ptr->next->prev = ptr;
  200.  
  201.     get_histogram(ptr);
  202.  
  203.  
  204.     /**** STEP 3: continually subdivide boxes until no more free boxes remain */
  205.  
  206.     while (freeboxes) {
  207.     ptr = largest_box();
  208.     if (ptr)
  209.         splitbox(ptr);
  210.     else
  211.         break;
  212.     }
  213.  
  214.  
  215.     /**** STEP 4: assign colors to all boxes ****/
  216.  
  217.     for (i = 0, ptr = usedboxes; i < num_colors && ptr; i++, ptr = ptr->next) {
  218.     assign_color(ptr, &r[i], &g[i], &b[i]);
  219.     }
  220.  
  221.     /* We're done with the boxes now */
  222.     num_colors = i;
  223.     free(box_list);
  224.     box_list = freeboxes = usedboxes = NULL;
  225.  
  226.  
  227.     /**** STEP 5: scan histogram and map all values to closest color */
  228.  
  229.     /* 5a: create cell list as described in Heckbert[2] */
  230.  
  231.     ColorCells = (CCELL **) calloc(C_LEN * C_LEN * C_LEN, sizeof(CCELL *));
  232.  
  233.  
  234.     /* 5b: create mapping from truncated pixel space to color table entries */
  235.  
  236.     map_colortable();
  237.  
  238.  
  239.     /**** STEP 6: scan image, match input values to table entries */
  240.  
  241.     i = quant_fsdither();
  242.  
  243.     /* free everything that can be freed */
  244.     free(ColorCells);
  245.  
  246.     get_global_cmap(rr, gg, bb);
  247.     return num_colors;
  248. }
  249.  
  250.  
  251. /****************************/
  252. get_global_cmap(rr, gg, bb)
  253.     byte     *rr, *gg, *bb;
  254. {
  255.     int       i;
  256.  
  257.     for (i = 0; i < 256; i++) {    /* pass back results */
  258.     rr[i] = r[i];
  259.     gg[i] = g[i];
  260.     bb[i] = b[i];
  261.     }
  262. }
  263.  
  264. /****************************/
  265. static void
  266. get_histogram(box)
  267.     CBOX     *box;
  268. /****************************/
  269. {
  270.     int       i, j, r, g, b, *ptr;
  271.     byte     *p;
  272.  
  273.     box->rmin = box->gmin = box->bmin = 999;
  274.     box->rmax = box->gmax = box->bmax = -1;
  275.     box->total = WIDE * HIGH;
  276.  
  277.     /* zero out histogram */
  278.     ptr = &histogram[0][0][0];
  279.     for (i = B_LEN * B_LEN * B_LEN; i > 0; i--)
  280.     *ptr++ = 0;
  281.  
  282.     /* calculate histogram */
  283.     p = pic24;
  284.     for (i = 0; i < HIGH; i++)
  285.     for (j = 0; j < WIDE; j++) {
  286.         r = (*p++) >> (COLOR_DEPTH - B_DEPTH);
  287.         g = (*p++) >> (COLOR_DEPTH - B_DEPTH);
  288.         b = (*p++) >> (COLOR_DEPTH - B_DEPTH);
  289.  
  290.         if (r < box->rmin)
  291.         box->rmin = r;
  292.         if (r > box->rmax)
  293.         box->rmax = r;
  294.  
  295.         if (g < box->gmin)
  296.         box->gmin = g;
  297.         if (g > box->gmax)
  298.         box->gmax = g;
  299.  
  300.         if (b < box->bmin)
  301.         box->bmin = b;
  302.         if (b > box->bmax)
  303.         box->bmax = b;
  304.         histogram[r][g][b]++;
  305.     }
  306. }
  307.  
  308.  
  309.  
  310. /******************************/
  311. static CBOX *
  312. largest_box()
  313. /******************************/
  314. {
  315.     CBOX     *tmp, *ptr;
  316.     int       size = -1;
  317.  
  318.     tmp = usedboxes;
  319.     ptr = NULL;
  320.  
  321.     while (tmp) {
  322.     if ((tmp->rmax > tmp->rmin ||
  323.          tmp->gmax > tmp->gmin ||
  324.          tmp->bmax > tmp->bmin) && tmp->total > size) {
  325.         ptr = tmp;
  326.         size = tmp->total;
  327.     }
  328.     tmp = tmp->next;
  329.     }
  330.     return (ptr);
  331. }
  332.  
  333.  
  334.  
  335. /******************************/
  336. static void
  337. splitbox(ptr)
  338.     CBOX     *ptr;
  339. /******************************/
  340. {
  341.     int       hist2[B_LEN], first, last, i, rdel, gdel, bdel;
  342.     CBOX     *new;
  343.     int      *iptr, *histp, ir, ig, ib;
  344.     int       rmin, rmax, gmin, gmax, bmin, bmax;
  345.     enum {
  346.     RED, GREEN, BLUE
  347.     }         which;
  348.  
  349.     /*
  350.      * see which axis is the largest, do a histogram along that axis.  Split
  351.      * at median point.  Contract both new boxes to fit points and return
  352.      */
  353.  
  354.     first = last = 0;        /* shut RT hcc compiler up */
  355.  
  356.     rmin = ptr->rmin;
  357.     rmax = ptr->rmax;
  358.     gmin = ptr->gmin;
  359.     gmax = ptr->gmax;
  360.     bmin = ptr->bmin;
  361.     bmax = ptr->bmax;
  362.  
  363.     rdel = rmax - rmin;
  364.     gdel = gmax - gmin;
  365.     bdel = bmax - bmin;
  366.  
  367.     if (rdel >= gdel && rdel >= bdel)
  368.     which = RED;
  369.     else if (gdel >= bdel)
  370.     which = GREEN;
  371.     else
  372.     which = BLUE;
  373.  
  374.     /* get histogram along longest axis */
  375.     switch (which) {
  376.  
  377.     case RED:
  378.     histp = &hist2[rmin];
  379.     for (ir = rmin; ir <= rmax; ir++) {
  380.         *histp = 0;
  381.         for (ig = gmin; ig <= gmax; ig++) {
  382.         iptr = &histogram[ir][ig][bmin];
  383.         for (ib = bmin; ib <= bmax; ib++) {
  384.             *histp += *iptr;
  385.             ++iptr;
  386.         }
  387.         }
  388.         ++histp;
  389.     }
  390.     first = rmin;
  391.     last = rmax;
  392.     break;
  393.  
  394.     case GREEN:
  395.     histp = &hist2[gmin];
  396.     for (ig = gmin; ig <= gmax; ig++) {
  397.         *histp = 0;
  398.         for (ir = rmin; ir <= rmax; ir++) {
  399.         iptr = &histogram[ir][ig][bmin];
  400.         for (ib = bmin; ib <= bmax; ib++) {
  401.             *histp += *iptr;
  402.             ++iptr;
  403.         }
  404.         }
  405.         ++histp;
  406.     }
  407.     first = gmin;
  408.     last = gmax;
  409.     break;
  410.  
  411.     case BLUE:
  412.     histp = &hist2[bmin];
  413.     for (ib = bmin; ib <= bmax; ib++) {
  414.         *histp = 0;
  415.         for (ir = rmin; ir <= rmax; ir++) {
  416.         iptr = &histogram[ir][gmin][ib];
  417.         for (ig = gmin; ig <= gmax; ig++) {
  418.             *histp += *iptr;
  419.             iptr += B_LEN;
  420.         }
  421.         }
  422.         ++histp;
  423.     }
  424.     first = bmin;
  425.     last = bmax;
  426.     break;
  427.     }
  428.  
  429.  
  430.     /* find median point */
  431.     {
  432.     int       sum, sum2;
  433.  
  434.     histp = &hist2[first];
  435.  
  436.     sum2 = ptr->total / 2;
  437.     histp = &hist2[first];
  438.     sum = 0;
  439.  
  440.     for (i = first; i <= last && (sum += *histp++) < sum2; i++);
  441.     if (i == first)
  442.         i++;
  443.     }
  444.  
  445.  
  446.     /* Create new box, re-allocate points */
  447.  
  448.     new = freeboxes;
  449.     freeboxes = new->next;
  450.     if (freeboxes)
  451.     freeboxes->prev = NULL;
  452.  
  453.     if (usedboxes)
  454.     usedboxes->prev = new;
  455.     new->next = usedboxes;
  456.     usedboxes = new;
  457.  
  458.     {
  459.     int       sum1, sum2, j;
  460.  
  461.     histp = &hist2[first];
  462.     sum1 = 0;
  463.     for (j = first; j < i; ++j)
  464.         sum1 += *histp++;
  465.     sum2 = 0;
  466.     for (j = i; j <= last; ++j)
  467.         sum2 += *histp++;
  468.     new->total = sum1;
  469.     ptr->total = sum2;
  470.     }
  471.  
  472.  
  473.     new->rmin = rmin;
  474.     new->rmax = rmax;
  475.     new->gmin = gmin;
  476.     new->gmax = gmax;
  477.     new->bmin = bmin;
  478.     new->bmax = bmax;
  479.  
  480.     switch (which) {
  481.     case RED:
  482.     new->rmax = i - 1;
  483.     ptr->rmin = i;
  484.     break;
  485.     case GREEN:
  486.     new->gmax = i - 1;
  487.     ptr->gmin = i;
  488.     break;
  489.     case BLUE:
  490.     new->bmax = i - 1;
  491.     ptr->bmin = i;
  492.     break;
  493.     }
  494.  
  495.     shrinkbox(new);
  496.     shrinkbox(ptr);
  497. }
  498.  
  499.  
  500. /****************************/
  501. static void
  502. shrinkbox(box)
  503.     CBOX     *box;
  504. /****************************/
  505. {
  506.     int      *histp, ir, ig, ib;
  507.     int       rmin, rmax, gmin, gmax, bmin, bmax;
  508.  
  509.     rmin = box->rmin;
  510.     rmax = box->rmax;
  511.     gmin = box->gmin;
  512.     gmax = box->gmax;
  513.     bmin = box->bmin;
  514.     bmax = box->bmax;
  515.  
  516.     if (rmax > rmin) {
  517.     for (ir = rmin; ir <= rmax; ir++)
  518.         for (ig = gmin; ig <= gmax; ig++) {
  519.         histp = &histogram[ir][ig][bmin];
  520.         for (ib = bmin; ib <= bmax; ib++)
  521.             if (*histp++ != 0) {
  522.             box->rmin = rmin = ir;
  523.             goto have_rmin;
  524.             }
  525.         }
  526.  
  527.       have_rmin:
  528.     if (rmax > rmin)
  529.         for (ir = rmax; ir >= rmin; --ir)
  530.         for (ig = gmin; ig <= gmax; ig++) {
  531.             histp = &histogram[ir][ig][bmin];
  532.             for (ib = bmin; ib <= bmax; ib++)
  533.             if (*histp++ != 0) {
  534.                 box->rmax = rmax = ir;
  535.                 goto have_rmax;
  536.             }
  537.         }
  538.     }
  539.   have_rmax:
  540.  
  541.     if (gmax > gmin) {
  542.     for (ig = gmin; ig <= gmax; ig++)
  543.         for (ir = rmin; ir <= rmax; ir++) {
  544.         histp = &histogram[ir][ig][bmin];
  545.         for (ib = bmin; ib <= bmax; ib++)
  546.             if (*histp++ != 0) {
  547.             box->gmin = gmin = ig;
  548.             goto have_gmin;
  549.             }
  550.         }
  551.       have_gmin:
  552.     if (gmax > gmin)
  553.         for (ig = gmax; ig >= gmin; --ig)
  554.         for (ir = rmin; ir <= rmax; ir++) {
  555.             histp = &histogram[ir][ig][bmin];
  556.             for (ib = bmin; ib <= bmax; ib++)
  557.             if (*histp++ != 0) {
  558.                 box->gmax = gmax = ig;
  559.                 goto have_gmax;
  560.             }
  561.         }
  562.     }
  563.   have_gmax:
  564.  
  565.     if (bmax > bmin) {
  566.     for (ib = bmin; ib <= bmax; ib++)
  567.         for (ir = rmin; ir <= rmax; ir++) {
  568.         histp = &histogram[ir][gmin][ib];
  569.         for (ig = gmin; ig <= gmax; ig++) {
  570.             if (*histp != 0) {
  571.             box->bmin = bmin = ib;
  572.             goto have_bmin;
  573.             }
  574.             histp += B_LEN;
  575.         }
  576.         }
  577.       have_bmin:
  578.     if (bmax > bmin)
  579.         for (ib = bmax; ib >= bmin; --ib)
  580.         for (ir = rmin; ir <= rmax; ir++) {
  581.             histp = &histogram[ir][gmin][ib];
  582.             for (ig = gmin; ig <= gmax; ig++) {
  583.             if (*histp != 0) {
  584.                 bmax = ib;
  585.                 goto have_bmax;
  586.             }
  587.             histp += B_LEN;
  588.             }
  589.         }
  590.     }
  591.   have_bmax:return;
  592. }
  593.  
  594.  
  595.  
  596. /*******************************/
  597. static void
  598. assign_color(ptr, rp, gp, bp)
  599.     CBOX     *ptr;
  600.     byte     *rp, *gp, *bp;
  601. /*******************************/
  602. {
  603.     /* +1 ensures that color represents the middle of the box */
  604.     *rp = ((ptr->rmin + ptr->rmax + 1) << (COLOR_DEPTH - B_DEPTH)) / 2;
  605.     *gp = ((ptr->gmin + ptr->gmax + 1) << (COLOR_DEPTH - B_DEPTH)) / 2;
  606.     *bp = ((ptr->bmin + ptr->bmax + 1) << (COLOR_DEPTH - B_DEPTH)) / 2;
  607. }
  608.  
  609.  
  610.  
  611. /*******************************/
  612. static CCELL *
  613. create_colorcell(r1, g1, b1)
  614.     int       r1, g1, b1;
  615. /*******************************/
  616. {
  617.     register int i, tmp, dist;
  618.     register CCELL *ptr;
  619.     register byte *rp, *gp, *bp;
  620.     int       ir, ig, ib, mindist;
  621.  
  622.     ir = r1 >> (COLOR_DEPTH - C_DEPTH);
  623.     ig = g1 >> (COLOR_DEPTH - C_DEPTH);
  624.     ib = b1 >> (COLOR_DEPTH - C_DEPTH);
  625.  
  626.     r1 &= ~1 << (COLOR_DEPTH - C_DEPTH);
  627.     g1 &= ~1 << (COLOR_DEPTH - C_DEPTH);
  628.     b1 &= ~1 << (COLOR_DEPTH - C_DEPTH);
  629.  
  630.     ptr = (CCELL *) malloc(sizeof(CCELL));
  631.     *(ColorCells + ir * C_LEN * C_LEN + ig * C_LEN + ib) = ptr;
  632.     ptr->num_ents = 0;
  633.  
  634.     /*
  635.      * step 1: find all colors inside this cell, while we're at it, find
  636.      * distance of centermost point to furthest corner
  637.      */
  638.  
  639.     mindist = 99999999;
  640.  
  641.     rp = r;
  642.     gp = g;
  643.     bp = b;
  644.     for (i = 0; i < num_colors; i++, rp++, gp++, bp++)
  645.     if (*rp >> (COLOR_DEPTH - C_DEPTH) == ir &&
  646.         *gp >> (COLOR_DEPTH - C_DEPTH) == ig &&
  647.         *bp >> (COLOR_DEPTH - C_DEPTH) == ib) {
  648.  
  649.         ptr->entries[ptr->num_ents][0] = i;
  650.         ptr->entries[ptr->num_ents][1] = 0;
  651.         ++ptr->num_ents;
  652.  
  653.         tmp = *rp - r1;
  654.         if (tmp < (MAX_COLOR / C_LEN / 2))
  655.         tmp = MAX_COLOR / C_LEN - 1 - tmp;
  656.         dist = tmp * tmp;
  657.  
  658.         tmp = *gp - g1;
  659.         if (tmp < (MAX_COLOR / C_LEN / 2))
  660.         tmp = MAX_COLOR / C_LEN - 1 - tmp;
  661.         dist += tmp * tmp;
  662.  
  663.         tmp = *bp - b1;
  664.         if (tmp < (MAX_COLOR / C_LEN / 2))
  665.         tmp = MAX_COLOR / C_LEN - 1 - tmp;
  666.         dist += tmp * tmp;
  667.  
  668.         if (dist < mindist)
  669.         mindist = dist;
  670.     }
  671.     /* step 3: find all points within that distance to box */
  672.  
  673.     rp = r;
  674.     gp = g;
  675.     bp = b;
  676.     for (i = 0; i < num_colors; i++, rp++, gp++, bp++)
  677.     if (*rp >> (COLOR_DEPTH - C_DEPTH) != ir ||
  678.         *gp >> (COLOR_DEPTH - C_DEPTH) != ig ||
  679.         *bp >> (COLOR_DEPTH - C_DEPTH) != ib) {
  680.  
  681.         dist = 0;
  682.  
  683.         if ((tmp = r1 - *rp) > 0 || (tmp = *rp - (r1 + MAX_COLOR / C_LEN - 1)) > 0)
  684.         dist += tmp * tmp;
  685.  
  686.         if ((tmp = g1 - *gp) > 0 || (tmp = *gp - (g1 + MAX_COLOR / C_LEN - 1)) > 0)
  687.         dist += tmp * tmp;
  688.  
  689.         if ((tmp = b1 - *bp) > 0 || (tmp = *bp - (b1 + MAX_COLOR / C_LEN - 1)) > 0)
  690.         dist += tmp * tmp;
  691.  
  692.         if (dist < mindist) {
  693.         ptr->entries[ptr->num_ents][0] = i;
  694.         ptr->entries[ptr->num_ents][1] = dist;
  695.         ++ptr->num_ents;
  696.         }
  697.     }
  698.     /* sort color cells by distance, use cheap exchange sort */
  699.     {
  700.     int       n, next_n;
  701.  
  702.     n = ptr->num_ents - 1;
  703.     while (n > 0) {
  704.         next_n = 0;
  705.         for (i = 0; i < n; ++i) {
  706.         if (ptr->entries[i][1] > ptr->entries[i + 1][1]) {
  707.             tmp = ptr->entries[i][0];
  708.             ptr->entries[i][0] = ptr->entries[i + 1][0];
  709.             ptr->entries[i + 1][0] = tmp;
  710.             tmp = ptr->entries[i][1];
  711.             ptr->entries[i][1] = ptr->entries[i + 1][1];
  712.             ptr->entries[i + 1][1] = tmp;
  713.             next_n = i;
  714.         }
  715.         }
  716.         n = next_n;
  717.     }
  718.     }
  719.     return (ptr);
  720. }
  721.  
  722.  
  723.  
  724.  
  725. /***************************/
  726. static void
  727. map_colortable()
  728. /***************************/
  729. {
  730.     int       ir, ig, ib, *histp;
  731.     CCELL    *cell;
  732.  
  733.     histp = &histogram[0][0][0];
  734.     for (ir = 0; ir < B_LEN; ir++)
  735.     for (ig = 0; ig < B_LEN; ig++)
  736.         for (ib = 0; ib < B_LEN; ib++) {
  737.         if (*histp == 0)
  738.             *histp = -1;
  739.         else {
  740.             int       i, j, tmp, d2, dist;
  741.  
  742.             cell = *(ColorCells +
  743.                  (((ir >> (B_DEPTH - C_DEPTH)) << C_DEPTH * 2)
  744.                   + ((ig >> (B_DEPTH - C_DEPTH)) << C_DEPTH)
  745.                   + (ib >> (B_DEPTH - C_DEPTH))));
  746.  
  747.             if (cell == NULL)
  748.             cell = create_colorcell(ir << (COLOR_DEPTH - B_DEPTH),
  749.                           ig << (COLOR_DEPTH - B_DEPTH),
  750.                          ib << (COLOR_DEPTH - B_DEPTH));
  751.  
  752.             dist = 9999999;
  753.             for (i = 0; i < cell->num_ents && dist > cell->entries[i][1]; i++) {
  754.             j = cell->entries[i][0];
  755.             d2 = r[j] - (ir << (COLOR_DEPTH - B_DEPTH));
  756.             d2 *= d2;
  757.             tmp = g[j] - (ig << (COLOR_DEPTH - B_DEPTH));
  758.             d2 += tmp * tmp;
  759.             tmp = b[j] - (ib << (COLOR_DEPTH - B_DEPTH));
  760.             d2 += tmp * tmp;
  761.             if (d2 < dist) {
  762.                 dist = d2;
  763.                 *histp = j;
  764.             }
  765.             }
  766.         }
  767.         histp++;
  768.         }
  769. }
  770.  
  771.  
  772.  
  773. /*****************************/
  774. static int
  775. quant_fsdither()
  776. /*****************************/
  777. {
  778.     register int *thisptr, *nextptr;
  779.     int      *thisline, *nextline, *tmpptr;
  780.     int       r1, g1, b1, r2, g2, b2;
  781.     int       i, j, imax, jmax, oval;
  782.     byte     *inptr, *outptr;
  783.     int       lastline, lastpixel;
  784.  
  785.     imax = HIGH - 1;
  786.     jmax = WIDE - 1;
  787.  
  788.     thisline = (int *) malloc(WIDE * 3 * sizeof(int));
  789.     nextline = (int *) malloc(WIDE * 3 * sizeof(int));
  790.  
  791.     if (thisline == NULL || nextline == NULL) {
  792.     fprintf(stderr, "%s: unable to allocate stuff for the 'dither' routine\n",
  793.         myname);
  794.     return 1;
  795.     }
  796.     inptr = (byte *) pic24;
  797.     outptr = (byte *) pic;
  798.  
  799.     /* get first line of picture */
  800.     for (j = WIDE * 3, tmpptr = nextline; j; j--)
  801.     *tmpptr++ = (int) *inptr++;
  802.  
  803.     for (i = 0; i < HIGH; i++) {
  804.     /* swap thisline and nextline */
  805.     tmpptr = thisline;
  806.     thisline = nextline;
  807.     nextline = tmpptr;
  808.     lastline = (i == imax);
  809.  
  810.     /* read in next line */
  811.     if (!lastline)
  812.         for (j = WIDE * 3, tmpptr = nextline; j; j--)
  813.         *tmpptr++ = (int) *inptr++;
  814.  
  815.     /* dither this line and put it into the output picture */
  816.     thisptr = thisline;
  817.     nextptr = nextline;
  818.  
  819.     for (j = 0; j < WIDE; j++) {
  820.         lastpixel = (j == jmax);
  821.  
  822.         r2 = *thisptr++;
  823.         g2 = *thisptr++;
  824.         b2 = *thisptr++;
  825.  
  826.         if (r2 < 0)
  827.         r2 = 0;
  828.         else if (r2 >= MAX_COLOR)
  829.         r2 = MAX_COLOR - 1;
  830.         if (g2 < 0)
  831.         g2 = 0;
  832.         else if (g2 >= MAX_COLOR)
  833.         g2 = MAX_COLOR - 1;
  834.         if (b2 < 0)
  835.         b2 = 0;
  836.         else if (b2 >= MAX_COLOR)
  837.         b2 = MAX_COLOR - 1;
  838.  
  839.         r1 = r2;
  840.         g1 = g2;
  841.         b1 = b2;
  842.  
  843.         r2 >> = (COLOR_DEPTH - B_DEPTH);
  844.         g2 >> = (COLOR_DEPTH - B_DEPTH);
  845.         b2 >> = (COLOR_DEPTH - B_DEPTH);
  846.  
  847.         if ((oval = histogram[r2][g2][b2]) == -1) {
  848.         int       ci, cj, dist, d2, tmp;
  849.         CCELL    *cell;
  850.  
  851.         cell = *(ColorCells +
  852.              (((r2 >> (B_DEPTH - C_DEPTH)) << C_DEPTH * 2)
  853.               + ((g2 >> (B_DEPTH - C_DEPTH)) << C_DEPTH)
  854.               + (b2 >> (B_DEPTH - C_DEPTH))));
  855.  
  856.         if (cell == NULL)
  857.             cell = create_colorcell(r1, g1, b1);
  858.  
  859.         dist = 9999999;
  860.         for (ci = 0; ci < cell->num_ents && dist > cell->entries[ci][1]; ci++) {
  861.             cj = cell->entries[ci][0];
  862.             d2 = (r[cj] >> (COLOR_DEPTH - B_DEPTH)) - r2;
  863.             d2 *= d2;
  864.             tmp = (g[cj] >> (COLOR_DEPTH - B_DEPTH)) - g2;
  865.             d2 += tmp * tmp;
  866.             tmp = (b[cj] >> (COLOR_DEPTH - B_DEPTH)) - b2;
  867.             d2 += tmp * tmp;
  868.             if (d2 < dist) {
  869.             dist = d2;
  870.             oval = cj;
  871.             }
  872.         }
  873.         histogram[r2][g2][b2] = oval;
  874.         }
  875.         *outptr++ = oval;
  876.  
  877.         r1 -= r[oval];
  878.         g1 -= g[oval];
  879.         b1 -= b[oval];
  880.  
  881.         r1 += 256;        /* make positive for table indexing */
  882.         g1 += 256;
  883.         b1 += 256;
  884.  
  885.         if (!lastpixel) {
  886.         thisptr[0] += tbl7[r1];
  887.         thisptr[1] += tbl7[g1];
  888.         thisptr[2] += tbl7[b1];
  889.         }
  890.         if (!lastline) {
  891.         if (j) {
  892.             nextptr[-3] += tbl3[r1];
  893.             nextptr[-2] += tbl3[g1];
  894.             nextptr[-1] += tbl3[b1];
  895.         }
  896.         nextptr[0] += tbl5[r1];
  897.         nextptr[1] += tbl5[g1];
  898.         nextptr[2] += tbl5[b1];
  899.  
  900.         if (!lastpixel) {
  901.             nextptr[3] += tbl1[r1];
  902.             nextptr[4] += tbl1[g1];
  903.             nextptr[5] += tbl1[b1];
  904.         }
  905.         nextptr += 3;
  906.         }
  907.     }
  908.     }
  909.     free(thisline);
  910.     free(nextline);
  911.     return 0;
  912. }
  913.  
  914.  
  915.  
  916.  
  917.  
  918. /************************************/
  919. static int
  920. Quick24to8(p24, w, h)
  921.     byte     *p24;
  922.     int       w, h;
  923. {
  924.  
  925.     /*
  926.      * floyd-steinberg dithering.
  927.      * 
  928.      * ----   x    7/16 3/16  5/16  1/16
  929.      * 
  930.      */
  931.  
  932.     /*
  933.      * called after 'pic' has been alloced, pWIDE,pHIGH set up, mono/1-bit
  934.      * checked already
  935.      */
  936.  
  937.     byte     *pp;
  938.     int       r1, g1, b1;
  939.     int      *thisline, *nextline, *thisptr, *nextptr, *tmpptr;
  940.     int       i, j, val, pwide3;
  941.     int       imax, jmax;
  942.  
  943.     pp = pic;
  944.     pwide3 = w * 3;
  945.     imax = h - 1;
  946.     jmax = w - 1;
  947.  
  948.     /* up to 256 colors:     3 bits R, 3 bits G, 2 bits B  (RRRGGGBB) */
  949. #define RMASK 0xe0
  950. #define R_SHIFT        0
  951. #define GMASK 0xe0
  952. #define G_SHIFT        3
  953. #define BMASK 0xc0
  954. #define B_SHIFT        6
  955.  
  956.     /* load up colormap */
  957.     /* note that 0 and 255 of each color are always in the map; */
  958.     /* intermediate values are evenly spaced. */
  959.     for (i = 0; i < 256; i++) {
  960.     r[i] = (((i << R_SHIFT) & RMASK) * 255 + RMASK / 2) / RMASK;
  961.     g[i] = (((i << G_SHIFT) & GMASK) * 255 + GMASK / 2) / GMASK;
  962.     b[i] = (((i << B_SHIFT) & BMASK) * 255 + BMASK / 2) / BMASK;
  963.     }
  964.  
  965.  
  966.     thisline = (int *) malloc(pwide3 * sizeof(int));
  967.     nextline = (int *) malloc(pwide3 * sizeof(int));
  968.     if (!thisline || !nextline) {
  969.     fprintf(stderr, "%s: unable to allocate memory in Quick24to8()\n", myname);
  970.     return (1);
  971.     }
  972.     /* get first line of picture */
  973.     for (j = pwide3, tmpptr = nextline; j; j--)
  974.     *tmpptr++ = (int) *p24++;
  975.  
  976.     for (i = 0; i < h; i++) {
  977.     tmpptr = thisline;
  978.     thisline = nextline;
  979.     nextline = tmpptr;    /* swap */
  980.  
  981.     if (i != imax)        /* get next line */
  982.         for (j = pwide3, tmpptr = nextline; j; j--)
  983.         *tmpptr++ = (int) *p24++;
  984.  
  985.     for (j = 0, thisptr = thisline, nextptr = nextline; j < w; j++, pp++) {
  986.         r1 = *thisptr++;
  987.         g1 = *thisptr++;
  988.         b1 = *thisptr++;
  989.         RANGE(r1, 0, 255);
  990.         RANGE(g1, 0, 255);
  991.         RANGE(b1, 0, 255);
  992.  
  993.         /* choose actual pixel value */
  994.         val = (((r1 & RMASK) >> R_SHIFT) | ((g1 & GMASK) >> G_SHIFT) |
  995.            ((b1 & BMASK) >> B_SHIFT));
  996.         *pp = val;
  997.  
  998.         /* compute color errors */
  999.         r1 -= r[val];
  1000.         g1 -= g[val];
  1001.         b1 -= b[val];
  1002.  
  1003.         /* Add fractions of errors to adjacent pixels */
  1004.         r1 += 256;        /* make positive for table indexing */
  1005.         g1 += 256;
  1006.         b1 += 256;
  1007.  
  1008.         if (j != jmax) {    /* adjust RIGHT pixel */
  1009.         thisptr[0] += tbl7[r1];
  1010.         thisptr[1] += tbl7[g1];
  1011.         thisptr[2] += tbl7[b1];
  1012.         }
  1013.         if (i != imax) {    /* do BOTTOM pixel */
  1014.         nextptr[0] += tbl5[r1];
  1015.         nextptr[1] += tbl5[g1];
  1016.         nextptr[2] += tbl5[b1];
  1017.  
  1018.         if (j > 0) {    /* do BOTTOM LEFT pixel */
  1019.             nextptr[-3] += tbl3[r1];
  1020.             nextptr[-2] += tbl3[g1];
  1021.             nextptr[-1] += tbl3[b1];
  1022.         }
  1023.         if (j != jmax) {/* do BOTTOM RIGHT pixel */
  1024.             nextptr[3] += tbl1[r1];
  1025.             nextptr[4] += tbl1[g1];
  1026.             nextptr[5] += tbl1[b1];
  1027.         }
  1028.         nextptr += 3;
  1029.         }
  1030.     }
  1031.     }
  1032.  
  1033.     return 0;
  1034. }
  1035.  
  1036.  
  1037.  
  1038. /****************************/
  1039. static int
  1040. QuickCheck(pic24, w, h, maxcol)
  1041.     byte     *pic24;
  1042.     int       w, h, maxcol;
  1043. {
  1044.     /*
  1045.      * scans picture until it finds more than 'maxcol' different colors.  If
  1046.      * it finds more than 'maxcol' colors, it returns '0'.  If it DOESN'T, it
  1047.      * does the 24-to-8 conversion by simply sticking the colors it found
  1048.      * into a colormap, and changing instances of a color in pic24 into
  1049.      * colormap indicies (in pic)
  1050.      */
  1051.  
  1052.     unsigned long colors[256], col;
  1053.     int       i, nc, low, high, mid;
  1054.     byte     *p, *pix;
  1055.  
  1056.     if (maxcol > 256)
  1057.     maxcol = 256;
  1058.  
  1059.     /* put the first color in the table by hand */
  1060.     nc = 0;
  1061.     mid = 0;
  1062.  
  1063.     for (i = w * h, p = pic24; i; i--) {
  1064.     col = (((u_long) * p++) << 16);
  1065.     col += (((u_long) * p++) << 8);
  1066.     col += *p++;
  1067.  
  1068.     /* binary search the 'colors' array to see if it's in there */
  1069.     low = 0;
  1070.     high = nc - 1;
  1071.     while (low <= high) {
  1072.         mid = (low + high) / 2;
  1073.         if (col < colors[mid])
  1074.         high = mid - 1;
  1075.         else if (col > colors[mid])
  1076.         low = mid + 1;
  1077.         else
  1078.         break;
  1079.     }
  1080.  
  1081.     if (high < low) {    /* didn't find color in list, add it. */
  1082.         /*
  1083.          * WARNING: this is an overlapped memory copy.  memcpy doesn't do
  1084.          * it correctly, hence 'bcopy', which claims to
  1085.          */
  1086.         if (nc >= maxcol)
  1087.         return 0;
  1088.         bcopy(&colors[low], &colors[low + 1], (nc - low) * sizeof(unsigned long));
  1089.         colors[low] = col;
  1090.         nc++;
  1091.     }
  1092.     }
  1093.  
  1094.  
  1095.     /*
  1096.      * run through the data a second time, this time mapping pixel values in
  1097.      * pic24 into colormap offsets into 'colors'
  1098.      */
  1099.  
  1100.     for (i = w * h, p = pic24, pix = pic; i; i--, pix++) {
  1101.     col = (((u_long) * p++) << 16);
  1102.     col += (((u_long) * p++) << 8);
  1103.     col += *p++;
  1104.  
  1105.     /* binary search the 'colors' array.  It *IS* in there */
  1106.     low = 0;
  1107.     high = nc - 1;
  1108.     while (low <= high) {
  1109.         mid = (low + high) / 2;
  1110.         if (col < colors[mid])
  1111.         high = mid - 1;
  1112.         else if (col > colors[mid])
  1113.         low = mid + 1;
  1114.         else
  1115.         break;
  1116.     }
  1117.  
  1118.     if (high < low) {
  1119.         fprintf(stderr, "QuickCheck:  impossible!\n");
  1120.         exit(1);
  1121.     }
  1122.     *pix = mid;
  1123.     }
  1124.  
  1125.     /* and load up the 'desired colormap' */
  1126.     for (i = 0; i < nc; i++) {
  1127.     r[i] = colors[i] >> 16;
  1128.     g[i] = (colors[i] >> 8) & 0xff;
  1129.     b[i] = colors[i] & 0xff;
  1130.     }
  1131.  
  1132.     return 1;
  1133. }
  1134.  
  1135. /**********************************************************************/
  1136. /**********************************************************************/
  1137. /**********************************************************************/
  1138.  
  1139. /*
  1140.  *   to_8.c   color quantizing routines
  1141.  *
  1142.  *   written by Guojun Jin, LBL
  1143.  */
  1144.  
  1145.  
  1146. #define      cmap_t  byte
  1147. #define      MaxColors       256
  1148. #define    RED    0
  1149. #define    GREEN    1
  1150. #define    BLUE    2
  1151. #define truncate(a, b, c)    { if (a<b) a=b;  else if (a>c) a=c; }
  1152.  
  1153. cmap_t   *reg_cmap[3];
  1154.  
  1155. static byte fsb_table[4][MaxColors];
  1156.  
  1157. /*********************************************************/
  1158. int
  1159. To_8(image, outbuf, width, height, max_colors, r, g, b)
  1160.     byte     *image, *outbuf;
  1161.     int       width, height, max_colors;
  1162.     cmap_t   *r, *b, *g;
  1163. {
  1164.     int       quant, i;
  1165.  
  1166.     if (reg_cmap[0] && pointer_buffer_size(reg_cmap[0]) < MaxColors * 3)
  1167.     free(reg_cmap[0]), reg_cmap[0] = NULL;
  1168.     if (reg_cmap[0] == NULL)
  1169.     reg_cmap[0] = (cmap_t *) calloc(MaxColors * 3, sizeof(cmap_t));
  1170.     reg_cmap[1] = reg_cmap[0] + MaxColors,
  1171.     reg_cmap[2] = reg_cmap[1] + MaxColors;
  1172.  
  1173.     quant = TrueCheck(image, outbuf, width * height, max_colors);
  1174.     if (quant < 0) {
  1175.     quant = dither_to8(image, outbuf, width, height);
  1176.     fprintf(stderr, "dithering required, %d colors in resulting color map \n", quant);
  1177.     } else {
  1178.     fprintf(stderr, "no dithering required, %d colors in image \n", quant);
  1179.     }
  1180.  
  1181.     for (i = 0; i < MaxColors; i++) {
  1182.     r[i] = reg_cmap[RED][i];
  1183.     g[i] = reg_cmap[GREEN][i];
  1184.     b[i] = reg_cmap[BLUE][i];
  1185.     }
  1186.  
  1187.     return quant;
  1188. }
  1189.  
  1190. /*********************************************************/
  1191. void
  1192. init_FS_tables()
  1193. {                /* initialize Floyd-Steinberg tables */
  1194.     register int i = MaxColors;
  1195.     while (i--) {
  1196.     fsb_table[0][i] = i >> 4;
  1197.     fsb_table[1][i] = 3 * i >> 4;
  1198.     fsb_table[2][i] = 5 * i >> 4;
  1199.     fsb_table[3][i] = 7 * i >> 4;
  1200.     }
  1201. }
  1202.  
  1203.  
  1204. /*********************************************************/
  1205. static
  1206. dither_to8(rgbp, obuf, w, h)
  1207.     byte     *rgbp, *obuf;
  1208.     int       w, h;
  1209. {
  1210.     int       r1, g1, b1;
  1211.     int      *thisline, *nextline, *thisptr, *nextptr, *tmpptr;
  1212.     int       i, j, rerr, gerr, berr, rgb_width = w * 3;
  1213.     int       imax = h - 1, jmax = w - 1;
  1214.     byte     *pp = obuf;
  1215.  
  1216.     for (i = 0; i < MaxColors; i++) {    /* build up colormap (RRRGGGBB)     */
  1217.     reg_cmap[RED][i] = ((i & 0xe0) * 255) / 0xe0;
  1218.     reg_cmap[GREEN][i] = ((i & 0x1c) * 255) / 0x1c;
  1219.     reg_cmap[BLUE][i] = ((i & 0x03) * 255) / 0x03;
  1220.     }
  1221.     /*
  1222.      * floyd-steinberg dithering.
  1223.      * 
  1224.      * ----   x    7/16 3/16  5/16  1/16
  1225.      */
  1226.     init_FS_tables();
  1227.  
  1228.     thisline = (int *) calloc(rgb_width, sizeof(int));
  1229.     nextline = (int *) calloc(rgb_width, sizeof(int));
  1230.  
  1231.     /* get first line of picture */
  1232.     for (j = rgb_width, tmpptr = nextline; j--;)
  1233.     *tmpptr++ = *rgbp++;
  1234.  
  1235.     for (i = 0; i < h; i++) {
  1236.     tmpptr = thisline;
  1237.     thisline = nextline;
  1238.     nextline = tmpptr;
  1239.  
  1240.     if (i != imax)        /* get next line */
  1241.         for (j = rgb_width, tmpptr = nextline; j--;)
  1242.         *tmpptr++ = *rgbp++;
  1243.  
  1244.     for (j = 0, thisptr = thisline, nextptr = nextline; j < w; j++, pp++) {
  1245.         r1 = *thisptr++;
  1246.         g1 = *thisptr++;
  1247.         b1 = *thisptr++;
  1248.         truncate(r1, 0, 255);
  1249.         truncate(g1, 0, 255);
  1250.         truncate(b1, 0, 255);
  1251.  
  1252.         rerr = r1 & 0x1F;
  1253.         gerr = g1 & 0x1F;
  1254.         berr = b1 & 0x3F;
  1255.         *pp = r1 & 0xE0 | (g1 >> 3) & 0x1C | (b1 >> 6);
  1256.  
  1257.         if (j != jmax) {    /* adjust RIGHT pixel */
  1258.         thisptr[0] += fsb_table[3][rerr];
  1259.         thisptr[1] += fsb_table[3][gerr];
  1260.         thisptr[2] += fsb_table[3][berr];
  1261.         }
  1262.         if (i != imax) {    /* do BOTTOM pixel */
  1263.         nextptr[0] += fsb_table[2][rerr];
  1264.         nextptr[1] += fsb_table[2][gerr];
  1265.         nextptr[2] += fsb_table[2][berr];
  1266.  
  1267.         if (j > 0) {    /* do BOTTOM LEFT pixel */
  1268.             nextptr[-3] += fsb_table[1][rerr];
  1269.             nextptr[-2] += fsb_table[1][gerr];
  1270.             nextptr[-1] += fsb_table[1][berr];
  1271.         }
  1272.         if (j != jmax) {/* do BOTTOM RIGHT pixel */
  1273.             nextptr[3] += fsb_table[0][rerr];
  1274.             nextptr[4] += fsb_table[0][gerr];
  1275.             nextptr[5] += fsb_table[0][berr];
  1276.         }
  1277.         nextptr += 3;
  1278.         }
  1279.     }
  1280.     }
  1281.     return MaxColors;
  1282. }
  1283.  
  1284. /*********************************************************/
  1285. static
  1286. TrueCheck(rgbp, obuf, fsize, maxcol)
  1287.     byte     *rgbp, *obuf;
  1288.     int       fsize, maxcol;
  1289. {
  1290.     long      colors[MaxColors], col;
  1291.     int       i, nc, low, high, mid;
  1292.     byte     *p, *pix;
  1293.  
  1294.     if (maxcol > MaxColors)
  1295.     maxcol = MaxColors;
  1296.  
  1297.     for (nc = mid = 0, i = fsize, p = rgbp; i--;) {
  1298.     col = *p++ << 16;
  1299.     col += *p++ << 8;
  1300.     col += *p++;
  1301.  
  1302.     /* binary search the 'colors' array to see if it's in there */
  1303.     low = 0;
  1304.     high = nc - 1;
  1305.     while (low <= high) {
  1306.         mid = (low + high) >> 1;
  1307.         if (col < colors[mid])
  1308.         high = mid - 1;
  1309.         else if (col > colors[mid])
  1310.         low = mid + 1;
  1311.         else
  1312.         break;
  1313.     }
  1314.  
  1315.     if (high < low) {    /* if not in list, add it. */
  1316.         if (nc >= maxcol)
  1317.         return -1;    /* quantizing will be required ! */
  1318.  
  1319.         /*
  1320.          * memcpy doesn't do overlapped copy correctly
  1321.          */
  1322.         bcopy(&colors[low], &colors[low + 1],
  1323.           (nc - low) * sizeof(unsigned long));
  1324.         colors[low] = col;
  1325.         nc++;
  1326.     }
  1327.     }
  1328.  
  1329.     /* run through the data a 2nd time, & convert to 8     */
  1330.     for (i = fsize, p = rgbp, pix = obuf; i--; pix++) {
  1331.     col = *p++ << 16;
  1332.     col += *p++ << 8;
  1333.     col += *p++;
  1334.  
  1335.     low = 0;
  1336.     high = nc - 1;
  1337.     while (low <= high) {
  1338.         mid = (low + high) >> 1;
  1339.         if (col < colors[mid])
  1340.         high = mid - 1;
  1341.         else if (col > colors[mid])
  1342.         low = mid + 1;
  1343.         else
  1344.         break;
  1345.     }
  1346.     if (high < low)
  1347.         fprintf(stderr, "TrueColor Check: double entry\n");
  1348.     *pix = mid;        /* set output */
  1349.     }
  1350.  
  1351.     for (i = nc; i--;) {    /* grab colormap */
  1352.     reg_cmap[RED][i] = (colors[i] >> 16) & 0xFF;
  1353.     reg_cmap[GREEN][i] = (colors[i] >> 8) & 0xFF;
  1354.     reg_cmap[BLUE][i] = colors[i] & 0xFF;
  1355.     }
  1356.     return nc;            /* quantizing not needed */
  1357. }
  1358.  
  1359. /***********************************************************/
  1360. pointer_buffer_size(p)        /* return the block size allocated for
  1361.                  * pointer *p */
  1362.     byte     *p;
  1363. {
  1364.     return *((int *) p - 2) - (sizeof(int) << 1);
  1365. }
  1366.